
//1870.准时到达的列车最小时速
class Solution {
    //检查是否满足条件
    //因为车都是在整数时间发车的所以要进行向上取整
    bool check(vector<int>& dist,double hour,int v)
    {
        int n=dist.size();
        double total=0;
        for(int i=0;i<n-1;i++)
        total+=(dist[i]-1)/v+1;

        total+=dist[n-1]/(double)v;
        return total<=hour;
    }

public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        //当速度越大时多需要的时间也短，可以使用二分的方式来求最小速率
        int n=dist.size();
        if(n-1>=hour) return -1;  //车次-1时因为最后一次算的是小数而并不需要取整
        long long left=0,right=ranges::max(dist);  //right用dist中的最大值替代，这样每辆车都只需要行驶一个小时
        double point=hour-(int)hour;            //如果最后一次出现小数时就需要对最后一次车速进行判断，来确定right是否需要扩大
        if(point!=0&&dist[n-1]/point>right) right=dist[n-1]/point+1;

        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(dist,hour,mid)) right=mid;
            else left=mid;
        }
        return right;
    }
};